#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "TableauDynamique.h"
#include "Element.h"

void initialisation_robuste_entier(int * e);
/* Preconditions : aucune
   Postconditions : e est initialise par une saisie clavier. En cas de saisie 
   invalide (par exemple "azerty" au lieu d'un nombre), une nouvelle saisie
   est demandee a l'utilisateur. Sortie du programme si l'utilisateur simule
   une fin de fichier (CTRL+D). */


void litFichierEntiers(const char * nomFicher, Tab_Dynamique * t);
/* Preconditions : nomFichier est une chaine de caracteres contenant le nom 
   d'un fichier texte, structure de la facon suivante :
     ------------------------
    |#nblignes: [entier]     |
    |[entier1]               |
    |[entier2]               |
    |[entier3]               |
    |[entier4]               |
    |..etc..                 |
    |[entier(nblignes)]      |
     ------------------------
   adrTab est l'adresse a laquelle est stockee un pointeur sur entier.

   Postconditions : un segment memoire assez grand pour stocker les (nblignes)
   entiers est reserve dans le tas. L'adresse de base de ce tableau est
   memorisee dans *adrTab. Les entiers stockes dans le fichier sont recopies
   dans le tableau. A charge pour le sous-programme appelant de liberer le
   tableau une fois tous les traitements effectues. 

   Resultat : retourne le nombre d'entiers lus (nblignes si tout va bien) */



void ecrireFichierEntiers(const char * nomFichier, Tab_Dynamique * t);
/* Preconditions : nomFichier est une chaine de caracteres contenant le nom 
   d'un fichier texte a creer dans le repertoire courant. tab est un tableau 
   contenant "taille" entiers. 
   Postconditions : un fichier texte nomme comme le contenu de la chaine nomFichier 
   est cree dans le repertoire courant. (Si ce fichier existe deja, son contenu 
   est ecrase). Ce fichier contient une premiere ligne de la forme "#nblignes: [entier]", 
   puis Les entiers contenus dans tab, a raison d'un entier par ligne. 
   Resultat : retourne le nombre d'entiers écrits avec succes. */


void triParSelectionDuMinimum(Tab_Dynamique * t);
/* Preconditions : tab est un tableau contenant "taille" entiers.
   Postconditions : les elements de tab sont ranges dans l'ordre croissant
   a l'aide de l'algorithme de tri par selection du minimum. */


void triParInsertion(Tab_Dynamique * t);
/* Preconditions : tab est un tableau contenant "taille" entiers.
   Postconditions : les elements de tab sont ranges dans l'ordre croissant
   a l'aide de l'algorithme de tri par insertion. */


void triParFusionInterne(Tab_Dynamique * t);
/* Preconditions : tab est un tableau contenant "taille" entiers.
   Postconditions : les elements de tab sont ranges dans l'ordre croissant
   a l'aide de l'algorithme de tri par fusion. */


void triParFusionExterne(const char * nomFic, const char * nomFicSortie);
/* Preconditions : nomFic est une chaine de caracteres contenant le nom 
   d'un fichier texte, structure de la facon suivante :
     ------------------------
    |#nblignes: [entier]     |
    |[entier1]               |
    |[entier2]               |
    |[entier3]               |
    |[entier4]               |
    |..etc..                 |
    |[entier(nblignes)]      |
     ------------------------
   nomFicSortie est le nom d'un fichier texte a creer dans le repertoire
   courant.

   Postconditions : un fichier texte nomme comme la chaine contenue dans 
   nomFicSortie est cree dans le repertoire courant. (Si un fichier de ce
   nom existait deja, il est ecrase). Ce fichier contient les memes entiers
   que le fichier d'entree, mais ceux-ci sont tries dans l'ordre croissant.
   Le tri est externe : on ne charge pas en memoire vive l'ensemble du 
   fichier, et on accede sequentiellement aux elements. 
 */






int main()
{
  Tab_Dynamique t;
  int algo = -1;
  char nomFic[101];
  char nomFicTrie[111];
  clock_t heureDebut, heureFin;


  /* Saisie du nom de fichier a lire */
  printf("Tapez le nom du fichier a trier (100 caracteres max) :\n");
  scanf("%100s", nomFic);
  sprintf(nomFicTrie, "resultattri-%s", nomFic);
	initialiser(&t, 2);

  /* Saisie de l'algorithme de tri a utiliser */
  do
    {
      printf("\nChoisissez l'algorithme de tri a executer : \n");
      printf("0 : selection du minimum\n");
      printf("1 : insertion\n");
      printf("2 : fusion (interne)\n");
      printf("3 : fusion (externe)\n");
      initialisation_robuste_entier(&algo);
    }
  while ((algo < 0) || (algo > 3)); 
	

  heureDebut = clock();

if (algo < 3)
    {
      /* Ecrivez ici l'instruction pour lire le fichier, c'est-a-dire le charger dans le tableau */
      litFichierEntiers(nomFic, &t);
   
      
      switch(algo)
        {
        case 0: {triParSelectionDuMinimum(&t); break;}
        case 1: {triParInsertion(&t); break;}
        case 2: {triParFusionInterne(&t); break;}
        }

      /* Ecrivez ici l'instruction pour ecrire le fichier trie */
      ecrireFichierEntiers(nomFicTrie, &t);

    }
  else
    {
      triParFusionExterne(nomFic, nomFicTrie);
    }

  heureFin = clock();
  

  /* Afficher le temps ecoule */
  printf("Temps d'execution: %f secondes.\n", ((float)(heureFin - heureDebut))/CLOCKS_PER_SEC);

	testament(&t);

  exit(EXIT_SUCCESS);
}





void litFichierEntiers(const char * nomFichier, Tab_Dynamique *T)
{
	/* A COMPLETER */
	int e,valret;
	FILE * monFic;
	monFic = fopen(nomFichier,"r");
	
	if(monFic == NULL)
	{
		printf("Impossible d’ouvrir le fichier\n");
		exit(EXIT_FAILURE);	
	}
	/* premiere ligne ! */	
	valret = fscanf(monFic,"#nblignes: %d",&e);
	if(valret != 1)
	{
		printf("Fin de fichier ou erreur de lecture \n ");
		exit(EXIT_FAILURE);	
	}
	/* Copie des entiers dans le tableau. */
	valret = fscanf(monFic, "%d", &e);	
	while(valret == 1)
	{	
		ajouteElement( T, e);
		valret = fscanf(monFic, "%d", &e);
	}
	fclose(monFic);
}

void ecrireFichierEntiers(const char * nomFichier, Tab_Dynamique * t)
{
	FILE * monFic;
	int i;
	monFic=fopen(nomFichier,"w");
	if(monFic==NULL)
	{
		printf("ouverture impossible\n");
	exit(EXIT_FAILURE);
	}
	for(i=0; i < t->derniere_position ; i++ )
	{	
		fprintf(monFic,"%d\n",t->ad[i]);
	}
	fclose(monFic);
}






void initialisation_robuste_entier(int * e) 
{
  int valretour ;	
  char c;
  valretour = scanf("%d", e); 
  while (valretour != 1) 
    {
      if(valretour == EOF)
	{
	  /* CTRL+D sur un buffer vide */
	  printf("Initialisation impossible 1 (fin de fichier)\n");
	  exit(EXIT_FAILURE);
	}

      /* printf("Caractere invalide, je vide le buffer... \n"); */

      do 
	{
	  valretour = scanf("%c",&c);
	}
      while((c!='\n') && (valretour != EOF));

      if(valretour == EOF)
	{
	  /* le buffer contenait des caractères invalides puis CTRL+D */
	  printf("Initialisation impossible 2 (fin de fichier)\n");
	  exit(EXIT_FAILURE);
	}

      printf("Recommencez votre saisie : \n");
      valretour = scanf("%d", e);
    }
}





void triParSelectionDuMinimum(Tab_Dynamique * t)
{
  int i, j;
  int indmin;
  int min;

  for(i = 0; i < t->derniere_position - 1; i++)
    {
      indmin = i;
      for(j = i+1; j < t->derniere_position; j++)
        {
          if (t->ad[j] < t->ad[indmin])
            {
              indmin = j;
            }
        }
      min =  t->ad[indmin];
      t->ad[indmin] = t->ad[i];
      t->ad[i] = min;
    }
}





void triParInsertion(Tab_Dynamique * t)
{
  int i, j;
  int elt_a_placer;
  
  for(j = 1; j < t->derniere_position; j++)
    {
      elt_a_placer = t->ad[j];
      i = j - 1;
      while ((i >= 0) && ( t->ad[i] > elt_a_placer))
        {
        	t->ad[i+1] = t->ad[i];
          i--;
        }
     	t->ad[i+1] = elt_a_placer;
    }
}

/* On fait le traitement a moitie sur place. Lors de la fusion, 
   on effectue une copie de la premiere monotonie en memoire temporaire 
   (on peut faire une copie des deux monotonies, mais ce n'est pas necessaire). 
   Ainsi, lors de la fusion, on a pas besoin de decaler les donnees, on copie 
   simplement un element de la premiere liste (depuis la memoire temporaire) ou 
   de la deuxieme liste (qui est gardee sur place). */
void triParFusionInterne(Tab_Dynamique * t)
{
 	Element * tmp;
	int debutMono1, debutMono2;
	int nbMono1traites, nbMono2traites;
	int lgMono = 1;
	int i,j,k;
	while (lgMono < t->derniere_position)
	{
		tmp = (Element *) malloc(lgMono * sizeof(Element));
		debutMono1 = 0;
		debutMono2 = debutMono1 + lgMono;
		
		while (debutMono2 < t->derniere_position) /* tant qu'on a une paire de monotonies a fusionner */
		{
		k = debutMono1;  /* index dans tab */
		i = 0;           /* index dans tmp */
		while(k < debutMono2)
		{
			tmp[i] = t->ad[k];
			i++;
			k++;
		}

		/* On fusionne les deux monotonies */
		/* Attentifon, la seconde peut être incomplete */
		i = 0;             /* index dans tmp, monotonie 1 */
		j = debutMono2;    /* index dans tab, monotonie 2 */
		k = debutMono1;    /* index dans tab, monotonie fusionnee */
		nbMono1traites = nbMono2traites = 0;
		while((nbMono1traites < lgMono) && (nbMono2traites < lgMono) && (j < t->derniere_position)) 
                /* tant qu'aucune monotonie n'est epuisee */
		{
			
			if(tmp[i] <= t->ad[j])
			{
				t->ad[k] = tmp[i];
				i++;
				k++;
				nbMono1traites++;
			}
			else
			{
				t->ad[k] = t->ad[j];
				j++;
			 	k++;
			 	nbMono2traites++;
			 }
		}
          


		if ((nbMono2traites == lgMono) || (j == t->derniere_position))
		{
       while(nbMono1traites < lgMono)
       {
       	t->ad[k] = tmp[i];
				i++;
				k++;
				nbMono1traites++;
       }
    }
		
		debutMono1 += (2*lgMono);
		debutMono2 += (2*lgMono);
        }
	free(tmp);
	lgMono *= 2;
    }
}


void triParFusionExterne(const char * nomFic, const char * nomFicSortie)
{
/*
  int nbMonotonies;
  int longueur = 1;
  char nomA[] = "fichierAnnexeA.txt";
  char nomB[] = "fichierAnnexeB.txt";
  FILE * fic, *ficSortie;
  int e;*/
  
  /* On cree une copie du fichier, sur laquelle l'algo va travailler */
  /* On enleve la ligne avec le nombre de lignes pour simplifier 
     les procedures eclatement et fusionExterne */

  /*fic = fopen(nomFic, "r");
  if (fic == NULL)
    {
      fprintf(stderr, "Erreur, impossible d'ouvrir le fichier %s\n", nomFic);
      return;
    }
  
  ficSortie = fopen(nomFicSortie, "w");
  if (ficSortie == NULL)
    {
      fprintf(stderr, "Erreur, impossible d'ouvrir le fichier %s\n", nomFic);
      return;
    }

  if (fscanf(fic, "#nblignes: %d", &e) != 1) 
    {
      fprintf(stderr, "Erreur de format\n");
      return;
    }

  while(fscanf(fic, "%d", &e) == 1)
    {
      fprintf(ficSortie, "%d\n", e);
    }

  fclose(fic);
  fclose(ficSortie);

  do
    {
      eclatement(nomFicSortie, longueur, nomA, nomB);
      fusionExterne(nomA, nomB, longueur, nomFicSortie, &nbMonotonies);
      longueur *= 2;
    } 
  while (nbMonotonies > 1);*/

  
}


